Because of the popularity of XML as a data exchange format that supports hierarchical relationships among elements, and because of the power of relational database management systems (DBMSs) to update and retrieve data, there is a demand for generating XML data output from relational databases and storing XML data into relational databases.
XPath is a language for addressing XML documents. XPath also provides basic facilities for manipulation of strings, numbers and Booleans. XPath operates on the abstract, logical structure of an XML document, rather than its surface syntax. XPath gets its name from its use of a path notation, as in URLs, for navigating through the hierarchical structure of an XML document.
The primary syntactic construct in XPath is the expression, which is evaluated to yield an object. XPath expressions are described in Section 3 (“Expressions”) of “XML Path Language (XPath)” (version 1.0). One important kind of expression is a location path. A location path selects a set of nodes relative to a context node. The result of evaluating an expression that is a location path is the node-set containing the nodes selected by the location path. Location paths can recursively contain expressions that are used to filter sets of nodes. The semantics of location paths are described in Section 2 (“Location Paths”) of “XML Path Language (XPath)” (version 1.0).
To be used in querying XML documents in a database, an XPath expression must be converted to statements that conform to the database language supported by the database server that manages the database. Structured Query Language (SQL) is a database language supported by many database servers. Thus, for an XPath expression to be used to query XML documents managed by a database server that supports SQL, the XPath expression must be converted to statements that conform to the SQL language (“SQL statements”).
According to contemporary implementations, in order to convert XPath expressions into SQL statements, the XPath expression is broken up into a linked list of path components. FIG. 1 gives an example XPath expression with a corresponding block diagram of how the XPath expression was evaluated according to prior art. XPath expression 110 is parsed into path components a and b, and, within path component b, there is a predicate c=1. Consequently, the only way to evaluate such XPath expressions is by running through this parsed representation and calling an evaluation function for each parsed component. This “functional” approach of evaluation not only suffers from lengthy processing times, it is also unable to benefit from more optimal execution strategies.
Based on the foregoing, it is clearly desirable to provide techniques to reduce the processing time of XPath expressions.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.